1. Field of the Invention
Aspects of the present invention relate to a file system, and more particularly, to a method and apparatus for allocating disc space for recording files.
2. Description of the Related Art
A variety of file systems (such as FAT, XFS, and Ext2) aim at storing a file in a disc such that the data elements of the file can be recorded as close together as possible, thus minimizing the time for a disc head to seek the file. In order to store the data of the file in close proximity to one another, empty disc space must be appropriately allocated.
FIG. 1 is a diagram explaining a conventional method of allocating empty disc space. Referring to FIG. 1, reference characters a through j indicate blocks. The size of the blocks a through j vary from one file system to another. Referring to FIG. 1, dark blocks indicate blocks to which data has already been allocated, and white blocks indicate empty blocks. A reference point indicates a location where data to be stored (target data) and data related to the target data have been most recently stored (i.e., a location where a disc head is currently located to read the target data).
A seek time becomes longer as the distance from the reference point becomes greater. Accordingly, a sufficient number of empty blocks to cover the size of the target data are allocated in increasing order of distance from the reference point. Referring to FIG. 1, the white blocks d, f, i, and j are sequentially allocated from the reference point.
However, when a file to be read is distributed over a plurality of blocks, the distances between a reference point and the blocks are not necessarily proportional to the time taken to seek the file. In general, the time taken to seek a file that is distributed over a plurality of consecutive blocks is shorter than the time taken to seek a file that is distributed over a plurality of nonconsecutive blocks. Thus, when data related to a file is distributed over a plurality of blocks, an exact seek time can be determined according to a seek curve of a file system. For example, referring to FIG. 1, assuming that the size of the target data amounts to the size of two blocks combined, the shortest seek time can be guaranteed by allocating the blocks i and j to the target data. However, according to the conventional method of allocating, empty blocks are allocated to the target data simply based on their distances from the reference point. Thus, the blocks d and f, instead of the blocks i and j, are allocated to the target data, thereby failing to provide an optimum block allocation.